#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;

int bfs(string s, string e, vector<string>& b);

int minMutation(string startGene, string endGene, vector<string>& bank)
{
    int ret = bfs(startGene, endGene, bank);
    return ret;
}

int bfs(string s, string e, vector<string>& b)
{
    unordered_map<string, int> hash1;
    unordered_map<string, int> hash2;
    queue<string> q;
    char a[4] = { 'A','C','G','T' };
    int count = 0;
    hash1[s]++;
    for (auto& e : b)
    {
        hash2[e]++;
    }
    q.push(s);
    while (q.size())
    {
        int sz = q.size();
        count++;
        for (int i = 0; i < sz; i++)
        {
            string sq = q.front();
            q.pop();
            for (int j = 0; j < s.size(); j++)
            {
                string temp = sq;
                for (int k = 0; k < 4; k++)
                {
                    temp[j] = a[k];
                    if (hash2[temp] > 0 && hash1[temp] == 0)
                    {
                        if (temp == e)
                        {
                            return count;
                        }
                        q.push(temp);
                        hash1[temp]++;
                    }
                }
            }
        }
    }
    return -1;
}
